﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace AlgoritmoAEstrella
{
    public partial class _8Puzzle : Form
    {
        public _8Puzzle()
        {
            InitializeComponent();
        }

        #region Metodos

        public void ResolverAlgoritmo()
        {
            int[] puzzle = new int[9];
            Movimientos movAnt = new Movimientos();
            bool primeraEjecucion = true;

            // comienzo la iteracion         
            do
            {
                // cargo el puzzle con los valores que contienen los textBox
                puzzle = this.CargarPuzzle();

                int pos=0;
                // recupero los movimientos posibles para el puzzle actual
                // paso por Referencia pos para poder recuperar la posicion del elemento a mover
                Movimientos[] mov = this.BuscarMovimientos(puzzle, ref pos);
                

                if (!primeraEjecucion)
                {
                    int h = 0;
                    bool b = true;

                    foreach (Movimientos m in mov) // consulto si entre los movimientos se encuentra el moviento anterior
                    {
                        if (m == movAnt)
                        {
                            b = false; // si esta incluido el movimiento anterior en mov
                            break;
                        }
                    }
                    Movimientos[] mov2;
                    if (!b) // si el movimiento anterior esta incluido en mov
                    {
                        // defino un segundo arreglo de una dimension menor
                        mov2 = new Movimientos[mov.LongLength - 1]; 
                    }
                    else
                    {
                        mov2 = new Movimientos[mov.LongLength];
                    }

                    foreach (Movimientos m in mov) // cargo el nuevo arreglo mov2 con los movimientos sin el anterior
                    {   
                        if (m != movAnt)
                        {
                            mov2[h] = m;
                            h++;
                        }
                    }

                    mov = mov2;
                }

                // defino un arreglo que contendra las distancias para los distintos movimientos
                int[] dist = new int[mov.LongLength];
                int i=0;

                foreach (Movimientos m in mov) // recorro el arreglo de movimientos posibles
                {
                    // creo un nuevo puzzle auxiliar con el movimiento realizado
                    int[] puzzleAux = this.MoverPuzzle(m, pos, puzzle);

                    // calculo la distancia de manhatan para dicho movimiento
                    //dist[i] = this.DistanciaManhatanPuzzle(puzzleAux);

                    // calculo la distancia de  manhatan
                    Distancia distancia = new Distancia();
                    dist[i] = distancia.DevuelveDistancia(puzzleAux);
            
                    i++;
                }

                int d = dist[0];
                int ind = 0;
                // busco la menor distancia de manhatan y guardo la posicion del movimiento que provoco la menor distancia
                for (int j = 1; j < dist.LongLength; j++)  // ver si es < o <= ????
                {
                    if (dist[j] < d)
                    {
                        d = dist[j];
                        ind = j;
                    }
                }

                // luego de analizar todos los movimientos
                // realizo el movimiento que provoca la menor distancia de manhatan
                puzzle = this.MoverPuzzle(mov[ind], pos, puzzle);

                movAnt = mov[ind];
                // imprimo el movimiento en el textBox
                this.txtMovimientos.Text += movAnt.ToString() + "\r\n";

                primeraEjecucion = false;

                this.GuardarPuzzle(puzzle);
                // this.PuzzleSoloLectura(true);

            }while (!this.VerificarCondicionFin(puzzle)); // mientras el puzzle no sea correcto seguire iterando          

            lblResultado.Visible = true;
        }

        // cargo los datos del puzzle
        public int[] CargarPuzzle()
        {
            int[] puzzle = new int[9];

            puzzle[0] = Int32.Parse(txt1.Text);
            puzzle[1] = Int32.Parse(txt2.Text);
            puzzle[2] = Int32.Parse(txt3.Text);
            puzzle[3] = Int32.Parse(txt4.Text);
            puzzle[4] = Int32.Parse(txt5.Text);
            puzzle[5] = Int32.Parse(txt6.Text);
            puzzle[6] = Int32.Parse(txt7.Text);
            puzzle[7] = Int32.Parse(txt8.Text);
            puzzle[8] = Int32.Parse(txt9.Text);

            return puzzle;
        }

        // metodo que carga el nuevo puzzle generado
        public void GuardarPuzzle(int[] puzzle)
        {
            // asigno a los textBox los valores del puzzle
            this.txt1.Text = puzzle[0].ToString();
            this.txt2.Text = puzzle[1].ToString();
            this.txt3.Text = puzzle[2].ToString();
            this.txt4.Text = puzzle[3].ToString();
            this.txt5.Text = puzzle[4].ToString();
            this.txt6.Text = puzzle[5].ToString();
            this.txt7.Text = puzzle[6].ToString();
            this.txt8.Text = puzzle[7].ToString();
            this.txt9.Text = puzzle[8].ToString();
        }

        // metodo que setea la propiedad ReadOnly de los textBox
        public void PuzzleSoloLectura(bool b)
        {
            // asigno a los textBox el valor booleano que paso por parametro
            this.txt1.ReadOnly = b;
            this.txt2.ReadOnly = b;
            this.txt3.ReadOnly = b;
            this.txt4.ReadOnly = b;
            this.txt5.ReadOnly = b;
            this.txt6.ReadOnly = b;
            this.txt7.ReadOnly = b;
            this.txt8.ReadOnly = b;
            this.txt9.ReadOnly = b;
        }

        // metodo que busca los posibles movimientos a realizar, dependiendo de donde este ubicado el 0;
        // paso por parametro la Posicion a mover
        public Movimientos[] BuscarMovimientos(int[] puzzle, ref int pos)
        {
            Movimientos[] mov; // = new Movimientos[4];
            if (puzzle[0] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 0
            {
                pos = 0; // guardo cual es la posicion a mover
                mov = new Movimientos[2];
                mov[0] = Movimientos.Derecha;
                mov[1] = Movimientos.Abajo;
            }
            else if (puzzle[1] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 1
            {
                pos = 1;
                mov = new Movimientos[3];
                mov[0] = Movimientos.Derecha;
                mov[1] = Movimientos.Izquierda;
                mov[2] = Movimientos.Abajo;
            }
            else if (puzzle[2] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 2
            {
                pos = 2;
                mov = new Movimientos[2];
                mov[0] = Movimientos.Izquierda;
                mov[1] = Movimientos.Abajo;
            }
            else if (puzzle[3] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 3
            {
                pos = 3;
                mov = new Movimientos[3];
                mov[0] = Movimientos.Arriba;
                mov[1] = Movimientos.Abajo;
                mov[2] = Movimientos.Derecha;
            }
            else if (puzzle[4] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 4
            {
                pos = 4;
                mov = new Movimientos[4];
                mov[0] = Movimientos.Arriba;
                mov[1] = Movimientos.Abajo;
                mov[2] = Movimientos.Derecha;
                mov[3] = Movimientos.Izquierda;
            }
            else if (puzzle[5] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 5
            {
                pos = 5;
                mov = new Movimientos[3];
                mov[0] = Movimientos.Arriba;
                mov[1] = Movimientos.Abajo;
                mov[2] = Movimientos.Izquierda;
            }
            else if (puzzle[6] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 6
            {
                pos = 6;
                mov = new Movimientos[2];
                mov[0] = Movimientos.Arriba;
                mov[1] = Movimientos.Derecha;
            }
            else if (puzzle[7] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 7
            {
                pos = 7;
                mov = new Movimientos[3];
                mov[0] = Movimientos.Arriba;
                mov[1] = Movimientos.Derecha;
                mov[2] = Movimientos.Izquierda;
            }
            else if (puzzle[8] == 0) // asigno los movimientos posibles si el 0 esta en la posicion 8
            {
                pos = 8;
                mov = new Movimientos[2];
                mov[0] = Movimientos.Arriba;
                mov[1] = Movimientos.Izquierda;
            }
            else mov = new Movimientos[0]; // para que no me ponga uso de variable no asiganada en el return

            return mov;
        }

        // metodo que calcula la distancia de manhatan para todo el puzzle
        public int DistanciaManhatanPuzzle(int[] puzzle)
        {
            int totalDistancia = 0;
            for (int i = 0; i < 9; i++)
            {
                if (puzzle[i] != 0) // valido que la posicion i no contenga el 0
                {
                    // recorro todo el puzzle y acumulo las distancias de manhatan
                    totalDistancia += this.DistanciaManhatanElemento(i, puzzle[i] - 1);
                }
                else
                {
                    // la la posicion i contiene el 0, paso por parametro el indice correcto que es el 8 (ultimo lugar)
                    totalDistancia += this.DistanciaManhatanElemento(i, 8);
                }
            }
            return totalDistancia;
        }

        // metodo que calcula la distancia de manhatan para un Elemento, se pasa por parametro su posicion actual y la correcta
        public int DistanciaManhatanElemento(int pos, int indiceCorrecto)
        {
            int resultado = 0;

            if (indiceCorrecto == pos + 0) // el numero esta correctamente ubicado
                resultado = 0; // distancia de manhatan 0
            else if (indiceCorrecto == pos + 1 || indiceCorrecto == pos + 3 || indiceCorrecto == pos - 1 || indiceCorrecto == pos - 3) // el numero esta a 1 salto de su posicion
                resultado = 1;// distancia manhatan 1
            else if (indiceCorrecto == pos + 2 || indiceCorrecto == pos + 4 || indiceCorrecto == pos + 6 ||
                indiceCorrecto == pos - 2 || indiceCorrecto == pos - 4 || indiceCorrecto == pos - 6)
                resultado = 2; // distancia manhatan 2
            else if (indiceCorrecto == pos + 5 || indiceCorrecto == pos + 7 || indiceCorrecto == pos - 5 || indiceCorrecto == pos - 7)
                resultado = 3; // distancia manhatan 3
            else if (indiceCorrecto == pos + 8 || indiceCorrecto == pos - 8)
                resultado = 4; // distancia manhatan 4

            return resultado;
        }

        // metodo que realiza el movimiento del puzzle que se pasa por parametro y retorna puzzle modificado
        public int[] MoverPuzzle(Movimientos mov, int pos, int[] puzzle)
        {
            int[] puzzcleAux = new int[9]; // = puzzle;
            int aux1, aux2;

            // copio el puzzle completo al puzzleAux
            for (int i = 0; i < 9; i++)
            {
                aux1 = puzzle[i];
                puzzcleAux[i] = aux1;
            }

            switch (mov) // valido que Tipo de movimiento es y realizo el cambio de posicion del 0 
            {
                case Movimientos.Abajo:
                    aux1 = puzzle[pos + 3];
                    aux2 = puzzle[pos];
                    puzzcleAux[pos + 3] = aux2;
                    puzzcleAux[pos] = aux1;
                    break;
                case Movimientos.Arriba:
                    aux1 = puzzle[pos - 3];
                    aux2 = puzzle[pos];
                    puzzcleAux[pos - 3] = aux2;
                    puzzcleAux[pos] = aux1;
                    break;
                case Movimientos.Derecha:
                    aux1 = puzzle[pos + 1];
                    aux2 = puzzle[pos];
                    puzzcleAux[pos + 1] = aux2;
                    puzzcleAux[pos] = aux1;
                    break;
                case Movimientos.Izquierda:
                    aux1 = puzzle[pos - 1];
                    aux2 = puzzle[pos];
                    puzzcleAux[pos - 1] = aux2;
                    puzzcleAux[pos] = aux1;
                    break;
            }

            return puzzcleAux;
        }

        // metodo que verifica si el puzzle pasado por parametro es correcto
        public bool VerificarCondicionFin(int[] puzzle)
        {
            bool ban = true;
            int[] puzzleOK = new int[9]{1,2,3,4,5,6,7,8,0};  // defino el puzzle  correcto

            for (int i = 0; i < 9; i++)
            {
                if(puzzle[i] != puzzleOK[i]) // valido que esten en el mismo orden los elementos del puzzle y el correcto
                {
                    ban = false;
                    break;
                }
            }

            return ban;
        }

        // metodo que limpia los textBox para comenzar nuevamente el programa
        public void LimpiarPuzzle()
        {
            txt1.Text = "";
            txt2.Text = "";
            txt3.Text = "";
            txt4.Text = "";
            txt5.Text = "";
            txt6.Text = "";
            txt7.Text = "";
            txt8.Text = "";
            txt9.Text = "";
            txtMovimientos.Text = "";
            lblResultado.Visible = false;
        }

        #endregion

        #region Eventos

        // evento que se dispara al presionar el boton Resolver
        private void btnResolver_Click(object sender, EventArgs e)
        {
            this.ResolverAlgoritmo();
        }

        // evento que se dispara al presionar Salir en el Menu
        private void salirToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.Close();
        }

        // evento que se dispara al presionar Reiniciar en el Menu
        private void reiniciarToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.LimpiarPuzzle();
        }

        // evento que se dispara la presionar Ayuda -> Algoritmo A*
        private void algoritmoAToolStripMenuItem_Click(object sender, EventArgs e)
        {
            string info = "ALGORITMO BUSQUEDA A*: \n\n" +
                "El algoritmo de búsqueda A* (pronunciado A asterisco o A estrella) se clasifica dentro de "+
                "los algoritmos de búsqueda en grafos. Presentado por primera vez en 1968 por Peter E. Hart, "+
                "Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas "+
                "determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo. "+
                "El problema de algunos algoritmos de búsqueda en grafos informados es que se guían en exclusiva "+
                "por la función heurística, la cual puede no indicar el camino de coste más bajo, o por el coste real "+
                "de desplazarse de un nodo a otro (como los algoritmos de escalada), pudiéndose dar el caso de que sea "+
                "necesario realizar un movimiento de coste mayor para alcanzar la solución. Es por ello bastante "+
                "intuitivo el hecho de que un buen algoritmo de búsqueda informada debería tener en cuenta ambos "+
                "factores, el valor heurístico de los nodos y el coste real del recorrido. \n\n" +
                "Fuente: Wikipedia, Algoritmo de búsqueda A*.";

            MessageBox.Show(info, "Ayuda", MessageBoxButtons.OK, MessageBoxIcon.Information);
        }

        #endregion

        #region Enumeraciones

        public enum Movimientos
        {
            Derecha,
            Izquierda,
            Arriba,
            Abajo
        }

        #endregion

        #region Clases Agus

        public class Distancia
        {
            public int DevuelveDistancia(int[] entrada)
            {
                //Convierto el string de entrada en una matriz 3x3
                int[,] matriz = new int[3, 3];
                int i = 0;
                for (int j = 0; j < 3; j++)
                {
                    for (int k = 0; k < 3; k++)
                    {
                        matriz[j, k] = entrada[i];
                        i++;
                    }
                }
                PosObjetivo PObj = new PosObjetivo();

                int distManh = 0;

                for (int k = 0; k < 3; k++)
                {
                    for (int j = 0; j < 3; j++)
                    {
                        distManh += Math.Abs(k - PObj.DevIndFila(matriz[k, j])) + Math.Abs(j - PObj.DevIndColu(matriz[k, j]));
                    }
                }

                return distManh;
            }
        }

        public class PosObjetivo
        {
            int[,] posicionObjetivo = new int[3, 3] {{1,2,3},
                                              {4,5,6},
                                              {7,8,0}};

            public int DevIndFila(int n)
            {
                for (int i = 0; i < 3; i++)
                {
                    for (int j = 0; j < 3; j++)
                    {
                        if (n == posicionObjetivo[i, j])
                        {
                            return i;
                        }
                    }
                }
                return -1; //Estaría fallando porque no encuentra el número. 
            }

            public int DevIndColu(int n)
            {
                for (int i = 0; i < 3; i++)
                {
                    for (int j = 0; j < 3; j++)
                    {
                        if (n == posicionObjetivo[i, j])
                        {
                            return j;
                        }
                    }
                }
                return -1; //Estaría fallando porque no encuentra el número. 
            }
        }

        #endregion




    }
}
